package main

import (
	"fmt"
	"sort"
)

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	var result [][]int
	var merged []int
	for _, v := range intervals {
		if len(merged) == 0 {
			merged = []int{v[0], v[1]}
		} else {
			if merged[1] >= v[0] {
				if merged[1] < v[1] {
					merged[1] = v[1]
				}
				// else: merged contains v
			} else {
				result = append(result, merged)
				merged = v
			}
		}
	}
	if merged != nil {
		result = append(result, merged)
	}
	return result
}

func main() {
	fmt.Printf("%#v\n", merge([][]int{
		{1, 3}, {2, 6}, {8, 10}, {15, 18},
	}))
	fmt.Printf("%#v\n", merge([][]int{
		{1, 4}, {4, 5},
	}))
	fmt.Printf("%#v\n", merge([][]int{
		{1, 4}, {2, 3},
	}))
}
